/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package progdynamique;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
 *
 * @author Guillaume
 */
public class ProgDynamiqueSolver {
    
    private DataProblem data;
    
    public ProgDynamiqueSolver(DataProblem data) {
        this.data = data;
    }
    
    public Solution solve(DataProblem dat){
        Solution solIncumbent = new Solution(dat.getNbItems());
        LinkedList<Label> listLabels = new LinkedList<>(); //For performance improvement (but space larger)
        LinkedList<Label> listLabelsTemp = new LinkedList<>(); //For performance improvement (but space larger)
        //ArrayList<Label> listLabels = new ArrayList<>();
        Iterator<Label> iL;
        
        int n = dat.getNbItems();
        int i=-1;
        
        listLabels.add(new Label(0, 0, 0, solIncumbent));
        
        while(++i < n && !listLabels.isEmpty()){
            
            listLabelsTemp.clear();
            
            
            for(Label lab : listLabels){
                //Add all current possible labels with x[i]=0 for this stage.
                    Label labNew0 = new Label(  i,
                                                lab.getWeight(),
                                                lab.getProfit(),
                                                lab.getSolAssociated());

                    //remove labels in listLabelsTemp if they are dominated by labelNew0
                    iL = listLabelsTemp.iterator();
                    boolean isDominated = false;
                    while(iL.hasNext()){
                        Label labTemp = iL.next();
                        if(labNew0.isDominates(labTemp)){
                            isDominated = true;
                        }else{
                            iL.remove();
                        }
                    }

                    //add labelNew0 if it's not dominated by an element of listLabelTemp and if the
                    //  the weight of this label plus the relaxation of the knapsack problem on
                    //  the restants items is greater than the weight of the incumbent Solution.
                   if(!labNew0.isPartialPlusRelaxWorseThan(dat, solIncumbent.profit(dat))
                           && !isDominated){
                       listLabelsTemp.add(labNew0);
                   }
                
                //add all current possible labels with x[i]=1 for this stage.
                   double wTemp = lab.getWeight() + dat.getListItems().get(i).getWeight();
                   if(wTemp <= dat.getCapSac()){
                       double pTemp = lab.getProfit() + dat.getListItems().get(i).getProfit();
                       double[] x = lab.getSolAssociated().getItemsChoosen();
                        x[i]=1;
                        
                        Label labNew1 = new Label(   i,
                                                wTemp,
                                                pTemp,
                                                new Solution(x));

                        //remove labels in listLabelsTemp if they are dominated by labelNew1
                        iL = listLabelsTemp.iterator();
                        isDominated = false;
                        while(iL.hasNext()){
                            Label labTemp = iL.next();
                            if(labTemp.isDominates(labNew1)){
                                isDominated = true;
                            }else{
                                iL.remove();
                            }
                        }

                        //add labelNew1 if it's not dominated by an element of listLabelTemp and if the
                        //  the weight of this label plus the relaxation of the knapsack problem on
                        //  the restants items is greater than the weight of the incumbent Solution.
                       if(!labNew1.isPartialPlusRelaxWorseThan(dat, solIncumbent.profit(dat))
                               && !isDominated){
                           listLabelsTemp.add(labNew1);
                       }
                       
                   } //end for w + w_i <= W
            } //end for labels in listLabels
            
            //Create the new ListLabel
            listLabels.clear();
            for(Label lab : listLabelsTemp){
                if(lab.getProfit() > solIncumbent.profit(dat)){
                    solIncumbent = new Solution(lab.getSolAssociated());
                }
                listLabels.add(lab);
            }
            
        }//end for i < n
        
        return solIncumbent;
    }

}